public class Code {
    // 最长递增子序列

    public int lengthOfLIS(int[] nums) {
        // 需要注意的是，本题是一个 严格增长子序列 问题

        // 创建 dp 表
        // 初始化
        // 填表
        // 确定返回值

        // 创建一个 dp 表
        // dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长递增子序列的长度
        int n = nums.length;
        int[] dp = new int[n];

        // 这里的 dp 表中，对于 dp[i] 其中存在两种情况
        // 情况一：当长度为 1 ，此时说明 i 位置的元素自身作为一个子序列
        // 情况二：当长度大于 1 ，此时表示的是 i 位置之前的元素（i - 1,i - 2,i - 3... （之后就记录为 j ））组成的子序列的长度。这里的最终长度为 dp[j] + 1.
        // 此时我们初始化
        for(int i = 0; i < n; i++){
            // 这里将 dp 表中的元素全部初始化为 1 是为了便于后续加 1
            dp[i] = 1;
        }

        int ret = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
                // 此时找到 dp 表中的最大值作为返回值
                ret = Math.max(ret,dp[i]);
            }
        }
        return ret;
    }
}
